﻿// 4549. 做作业.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <vector>



using namespace std;


/*
https://www.acwing.com/problem/content/4552/

张华有 N科作业需要完成，每科作业都有一个上交作业的截止日期，以及完成该作业所需要的时间。

已知，如果某一科作业没有按时完成，在截止日期后才提交，就会被老师扣分，每晚 1天就要扣 1分。

作业要一科一科写，并且尽可能的少被扣分。

请你帮张华合理的安排他写作业的顺序，使得他被扣的分数尽可能少。

输入格式
第一行包含整数 T，表示共有 T组测试数据。

每组数据第一行包含一个整数 N。

接下来 N行，每行描述一个学科，首先包含一个由大小写字母构成的字符串 S
，表示学科名称，然后包含两个整数 D,C，表示科目的截止日期以及完成所需时间。

为了使数据更容易处理，所有学科按名称的字典顺序给出。

输出格式
每组数据首先输出一行，一个整数表示最少被扣分数。

随后 N行，输出扣分最少的写作业顺序方案，每行输出一科名称，如果方案不唯一，则输出科目名称字典序最小的方案。

数据范围
1≤T≤10,
1≤N≤15,
1≤|S|≤100,
1≤D,C≤1000。

输入样例：
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3


输出样例：
2
Computer
Math
English
3
Computer
English
Math
样例解释
对于第二组数据，Computer->English->Math 和 Computer->Math->English 都是最优方案，都只扣 3
 分。

但是，前者字典序更靠前，所以采用前一种方案。
2
15
A 1 1
B 2 1
C 3 1
D 4 1
E 5 1
F 6 1
G 7 1
H 8 1
I 9 1
J 10 1
K 11 1
L 12 1
M 13 1
N 14 1
O 15 1
3
Z 1 3
Y 2 4
X 3 5
*/

const int N = 16, M = 1 << 15;

vector<int> StateByOneCnt[N];
int costTime[M];
int dp[M];
int  t, n;

int prevStateArr[M];

struct CLASS {
	string name;
	int limit, need;
}classes[N];

bool cmp(const struct CLASS& a, const struct CLASS& b) {
	if (a.name < b.name) return true;
	else if (a.name == b.name) {
		if (a.limit < b.limit) return true;
		else if (a.limit == b.limit) return a.need < b.need;
	}
	return false;
}


int GetOneCnt(int state) {
	int ret = 0;

	while (state > 0) {
		if (state & 1) ret++;
		state >>= 1;
	}

	return ret;
}


int GetCostTime(int state) {
	int ret = 0;

	for (int i = 0; i < n; i++) {
		if ((state >> i) & 1) {
			ret += classes[i].need;
		}
	}

	return ret;
}


void solve() {

	memset(dp,0x3f,sizeof dp);
	memset(costTime,0x3f,sizeof costTime);
	for (int i = 0; i < N; i++) {	StateByOneCnt[i].clear();}
	for (int i = 0; i < N; i++) { classes[i].name = ""; classes[i].limit = 0; classes[i].need = 0; }

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> classes[i].name >> classes[i].limit >> classes[i].need;
	}

	sort(classes, classes+n,cmp);

	//预处理各种组合花费的时间和 各种组合中包含的课程数
	for (int i = 0; i <= (1<<n)-1; i++) {
		int idx = GetOneCnt(i);
		StateByOneCnt[idx].push_back(i);
		costTime[i] = GetCostTime(i);
	}

	dp[0] = 0;
	//T*N*N*M
	for (int i = 1; i <= n; i++) {
		int debug = 0;
		for (int j = 0; j < StateByOneCnt[i].size(); j++) {
			int state = StateByOneCnt[i][j];
			for (int k = n-1; k >=0 ; k--) {
				if ((state >> k) & 1) {
					int prev = state ^ (1 << k);
					int prevTime = costTime[prev];
					int cost = max(prevTime + classes[k].need - classes[k].limit, 0);
					//dp[state] = min(dp[state], dp[prev] + cost);
					if (dp[state] > dp[prev] + cost) {
						dp[state] = dp[prev] + cost;
						prevStateArr[state] = prev;
					}
				}
			}
			//cout << "dp[" << state << "] = " << dp[state] << endl;
		}
	}


	cout << dp[ (1 << n) - 1] << endl;
	int currstate = (1 << n) - 1;
	vector<string> ans;
	while (currstate != 0) {
		int prev = prevStateArr[currstate];
		int selState = currstate - prev;
		int idx = 0;
		while (((selState >> idx) & 1) == 0) {
			idx++;
		}
		ans.push_back(classes[idx].name);
		currstate = prev;
	}

	for (int i = ans.size() - 1; i >= 0; i--) {
		cout << ans[i] << endl;
	}

	return;
}

int main()
{
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

 